package Lee_code;

import java.util.*;

/**
 * @author blh
 * @date 2024年06月30日 10:14
 */
public class Lee_39_630 {
    List<List<Integer>> res = new LinkedList<>();
    int len;
    int end;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        len = candidates.length;
        end = target;
        Arrays.sort(candidates);
        backTrace(new ArrayList<Integer>(), 0, candidates);
        return res;
    }

    public void backTrace(ArrayList<Integer> list, int index, int[] candidates) {
        int sum = list.stream().mapToInt(Integer::intValue).sum();
        if (sum == end) {
            res.add(new ArrayList<>(list));
            return;
        } else if (sum > end) {
            return;
        }
        for (int i = index; i < len; i++) {
            list.add(candidates[i]);
            backTrace(list, i, candidates);
            list.remove(list.size()-1);
        }
    }
}
